package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/21.
 */
public class Least_K_Num {
    private List<Integer> rst= new LinkedList<Integer>();
    private void getLeast(int[] nums,int k){
        int tree = nums[0];
        int begin = 0,last = nums.length-1;
        while(begin<last){
            for(;last>begin && nums[last]>=tree;last--);
            nums[begin] = nums[last];
            for(;begin<last && nums[begin]<=tree;begin++);
            nums[last] = nums[begin];
        }
        nums[begin] = tree;
        if(begin+1<k){
            for(int i=0;i<begin+1;i++){
                rst.add(nums[i]);
            }
            int[] num = new int[nums.length-begin-1];
            for(int i=0;i<num.length;i++){
                num[i] = nums[begin+1+i];
            }
            getLeast(num,k-begin-1);
        }
        else if(begin+1==k){
            for(int i=0;i<begin+1;i++){
                rst.add(nums[i]);
            }
        }
        else{
            int[] num = new int[begin];
            for(int i=0;i<num.length;i++){
                num[i] = nums[i];
            }
            getLeast(num,k);
        }
    }
    public List<Integer> leastK(int[] nums,int K){
        if(K<=0)
            return rst;
        if(nums.length<=K){
            for(int i=0;i<nums.length;i++){
                rst.add(nums[i]);
            }
            return rst;
        }
        else{
            getLeast(nums,K);
            return rst;
        }
    }
    public static void main(String[] args){
        int[] num = {3,1,4,2,5,7,6};
        Least_K_Num least_k_num = new Least_K_Num();
        List<Integer> rst = least_k_num.leastK(num,0);
        System.out.println(rst);
    }
}
